package com.lucifer.sort;

/**
 * 快速排序
 *
 * @author yuxiao05@meituan.com
 * @create 2016-07-05 下午5:11
 */

public class QuickSort {
  public static void main(String[] args){
    int[] a = new int[]{2,1,4,5,3,2,6};

    quickSort(a, 0, a.length - 1);

    for (int i : a) {
      System.out.println(i);
    }
  }

  private static void swap(int arr[], int i, int j) {
    int tmp;

    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  public static void quickSort(int arr[], int left, int right) {
    int i, last;

    if (left > right)
      return;

    swap(arr, left, (left + right) >>> 1);
    last = left;
    for (i = left + 1; i <= right; i++) {
      if (arr[i] < arr[left])
        ++last;
    }
    swap(arr, left, last);
    quickSort(arr, left, last - 1);
    quickSort(arr, last + 1, right);
  }
}
